package 中等.拓扑排序;

import java.util.*;

/**
 * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一
 * 个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有
 * 最小高度的树（即，min(h)）被称为 最小高度树 。
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-height-trees
 */
public class 最小高度树_310 {

    public static void main(String[] args) {

//        int[][] edges = {{1, 0}, {1, 2}, {1, 3}};
//        int[][] edges = {{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}};
        int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}};
        System.out.println(findMinHeightTrees2(7, edges));

    }

    /**
     * 发现以越靠近树中心为根节点的树高度越小
     * 广度优先搜索
     * 以度为1的节点作为起始节点搜索，度为1 = 只有一条无向边
     * 思路：
     * 不断的将度为1的节点放入队列中，并且将每个节点的度进行更新，最后一层即为答案
     */
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> list = new ArrayList<>();
        if (edges.length == 0) {
            list.add(0);
            return list;
        }
        // 用来保存当前节点，连接了哪些节点
        Map<Integer, List<Integer>> mapNode = new HashMap<>();
        // 用来保存当前节点的度
        Map<Integer, Integer> mapDegree = new HashMap<>();
        for (int[] edge : edges) {
            int oneNode = edge[0];
            int twoNode = edge[1];
            // 数字出现一次 度+1
            mapDegree.put(oneNode, mapDegree.getOrDefault(oneNode, 0) + 1);
            mapDegree.put(twoNode, mapDegree.getOrDefault(twoNode, 0) + 1);
            List<Integer> oneChildNode = mapNode.getOrDefault(oneNode, new ArrayList<>());
            oneChildNode.add(twoNode);
            mapNode.put(oneNode, oneChildNode);
            // 互为子节点
            List<Integer> twoChildNode = mapNode.getOrDefault(twoNode, new ArrayList<>());
            twoChildNode.add(oneNode);
            mapNode.put(twoNode, twoChildNode);
        }
        Deque<Integer> queue = new ArrayDeque<>();
        // 找度为1的节点
        for (Integer node : mapDegree.keySet()) {
            if (mapDegree.get(node).equals(1)) {
                queue.addLast(node);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            list.clear();  // 需要清理上一层的节点
            while (size-- > 0) {
                Integer curNode = queue.pollFirst();
                list.add(curNode);
                for (Integer nextNode : mapNode.get(curNode)) {
                    // nextNode和curNode有一条无向线，curNode从队列中取出，相当于在无向图中取出curNode节点
                    mapDegree.put(nextNode, mapDegree.get(nextNode) - 1);
                    if (mapDegree.get(nextNode) == 1) {
                        queue.addLast(nextNode);
                    }
                }
            }
        }
        return list;
    }

    /**
     * 使用数组来模拟要快一些，无需哈希计算
     */
    public static List<Integer> findMinHeightTrees2(int n, int[][] edges) {
        List<Integer> list = new ArrayList<>();
        if (edges.length == 0) {
            list.add(0);
            return list;
        }
        // 用来保存当前节点，连接了哪些节点
        List<List<Integer>> mapNodeList = new ArrayList<>(200);
        for (int i = 0; i < n; i++) {
            mapNodeList.add(new ArrayList<>());  // 初始化数组
        }
        // 用来保存当前节点的度，直接用数组就不用，0 <= ai, bi < n
        int[] mapDegree = new int[n];
        for (int[] edge : edges) {
            // 数字出现一次 度+1
            mapDegree[edge[0]]++;
            mapDegree[edge[1]]++;
            // 互为邻节点
            mapNodeList.get(edge[0]).add(edge[1]);
            mapNodeList.get(edge[1]).add(edge[0]);
        }
        Deque<Integer> queue = new ArrayDeque<>();
        // 找度为1的节点
        for (int i = 0; i < mapDegree.length; i++) {
            if (mapDegree[i] == 1) {
                queue.addLast(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            list.clear();  // 需要清理上一层的节点
            while (size-- > 0) {
                Integer curNode = queue.pollFirst();
                list.add(curNode);
                for (Integer nextNode : mapNodeList.get(curNode)) {
                    // nextNode和curNode有一条无向线，curNode从队列中取出，相当于在无向图中取出curNode节点
                    mapDegree[nextNode]--;
                    if (mapDegree[nextNode] == 1) {
                        queue.addLast(nextNode);
                    }
                }
            }
        }
        return list;
    }

}
